Метод прогону Більшість технічних задач зводиться до розв’язування систем лінійних алгебраїчних рівнянь, в яких матриці містять багато нульових елементів, а ненульові елементи розміщені за спеціальною структурою (стрічкові квазітрикутні матриці). Задачі побудови інтерполяційних сплайнів, різницевих методів розв’язування крайових задач для диференціальних рівнянь зводяться до розв’язування систем лінійних алгебраїчних рівнянь з трьохдіагональною матрицею А. В матриці А всі елементи, що не лежать на головній діагоналі і двох сусідніх паралельних діагоналях, дорівнюють нулю. В загальному вигляді такі системи записують так: аіхі-1 + bixi + cixi+1 = di (1) 1 ≤ i ≤ n ; a1 = 0 ; cn = 0 або в розгорнутому вигляді: b1x1 + c1x2 = d1 a2x1 + b2x2 + c2x3 = d2 a3x2 + b3x3 + c3x4 = d3 ∙∙∙ ∙∙∙ ∙∙∙ ∙∙∙ ∙∙∙ ∙∙∙ ∙∙∙ ∙∙∙ ∙∙∙ ∙∙∙ ∙∙∙ ∙∙∙ ∙∙∙ ∙∙∙ ∙∙∙ ∙∙∙ ∙∙∙ ∙∙∙ ∙∙∙ ∙∙∙ (2) aixi-1 + bixi + cixi+1 = di an-1xn-2 + bn-1xn-1 + cn-1xn = dn-1 anxn-1 + bnxn = dn Вибір найбільшого елемента при виключенні невідомих за методом Гауса в таких системах робити не можна, оскільки перестановка рядків руйнує структуру матриці. Найчастіше для розв’язку системи з трьохдіагональною матрицею використовують метод прогону, який є частковим випадком методу Гауса. Прямий хід прогону (алгоритм прямого ходу методу Гауса). Кожне невідоме хі виражається через хі+1 з допомогою прогоночних коефіцієнтів Аі та Ві хі = Аіхі+1 + Ві ;
(3) Наприклад, з першого рівняння системи (2) знайдемо
, звідки
(4) З другого рівняння системи (3) виразимо х2 через х3, замінюючи х1 формулою (3) або (4) a2х1 + b2x2 + c2x3 = a2(A1x2 + B1) + b2x2 = d2 Звідси знайдемо
або х2 = А2х3 + В2

, беручи за е2 = а2А1 + b2 Запишемо:

Аналогічно для кожного і прогоночні коефіцієнти з рівняння хі = Аіхі+1 + Ві мають вигляд:

(5) еі = аіАі-1 + bі ;
При цьому враховуючи, що а1 = сn = 0 приймаємо Ао = 0 ; Во = 0. (6) В розгорнутому вигляді формула (5) буде мати вигляд формули (7). Значення прогоночних коефіцієнтів можна одержати і таким шляхом. В рівнянні (3) понизимо індекс на одиницю та підставимо значення хі-1 в і-е рівняння системи (1) хі-1 = Аі-1∙хі + Ві-1 аіхі-1 + bixi + cixi+1 = di
ai(Ai-1xi + Bi-1) + bixi + cixi+1 = di
(7) Обернений хід прогонки (аналог оберненого ходу методу Гауса). Він полягає в послідовному обчисленні невідомих хі. Спочатку знаходять хn. Для цього формулу (7) запишемо при і = n (враховуючи, що Cn =0)
Долі використовуючи формулу (3) знаходимо послідовно всі невідомі xn-1, xn-2, … , x1. Майже у всіх задачах, що приводять до розв’язку системи (2) з трьохдіаго-нальною матрицею, забезпечується умова переважання діагональних коефіцієнтів
Це забезпечує існування єдиного розв’язку та достатню стійкість методу прогону відносно похибок заокруглення. Для запису коефіцієнтів ai, bi, та прогоночних коефіцієнтів Аi-1, Ві-1 використати один і той же масив. Метод LU – розкладу (метод розкладу на трикутні матриці або метод LU – факторизації ) Алгоритми цього методу досить близькі до методу Гауса. Основна перевага методу LU – факторизації в порівнянні з методом Гауса є можливість більш простого одержання розв’язку для різних векторів b системи лінійних алгебраїчних рівнянь A · x = b, (1) A – матриця розміру n
n із сталими коефіц...